#ifndef DEJKSTRA_H_
#define DEJKSTRA_H_

#include <vector>
#include <binders.h>

#include <boost/noncopyable.hpp>
#include <boost/bind.hpp>

#include "graph_support/GraphSupport.h"

namespace GRAPH_SUPPORT_NS
{
namespace alg
{
namespace shortest_path
{

/**
 * solves the single source multiple destinations shortest path problem.
 * expects Graph::EdgeAttributes to satisfy GRAPH_SUPPORT_NS::impls::LengthEdgeAttributes
 */
template< typename GraphT >
class Dejkstra
{
private:
	typedef GraphT Graph;
	typedef typename Graph::GrVertex GrVertex;
	typedef typename Graph::GrEdge GrEdge;
	typedef typename Graph::GrEdgePtr GrEdgePtr;
	typedef typename Graph::EdgeAttributes EdgeAttributes;
	typedef typename EdgeAttributes::EdgeLength EdgeLength;
	typedef typename Graph::VertexIterator VertexIterator;
	typedef typename Graph::EdgeIterator EdgeIterator;

// TODO 9 [decide] separate dejkstra-result-data and dejkstra algorithm
public:
	Dejkstra( Graph & gr )
		: gr( gr )
		, dist( gr.getVertexCount(), EdgeAttributes::getINFLength() )
	{
	}

public:
	EdgeLength getDistance( const GrVertex & v )
	{
		size_t vid = gr.vert2num( v );
		return dist[vid];
	}

	void operator () ( const GrVertex & source )
	{
		size_t n = gr.getVertexCount();
		std::vector< char > knownBuf( n, ( char ) false );
		bool * known = ( bool * ) & knownBuf[0];

		size_t sourceId = gr.vert2num( source );
		dist[sourceId] = 0;
		for ( int dejkstraStep = 0; dejkstraStep < n; dejkstraStep++ )
		{
			bool * firstUnknownPtr = std::find_if( known, known + n,
					std::bind2nd( std::less_equal< bool >(), false ) );
			size_t firstUnknown = firstUnknownPtr - known;
			assert( firstUnknown == std::accumulate( known, firstUnknownPtr, 0 ) );
			assert( firstUnknown < n );
			assert( ! known[firstUnknown] );

			size_t minVertId = firstUnknown;
			for ( int i = firstUnknown + 1; i < n; i++ )
			{
				if ( ! known[i] && ( dist[minVertId] > dist[i] ) )
				{
					minVertId = i;
				}
			}
			known[minVertId] = true;

			EdgeIterator stopIt = gr.getEdgsEndId( minVertId );
			for ( EdgeIterator it = gr.getEdgsBegId( minVertId ); it != stopIt; ++it )
			{
				GrEdgePtr eptr = * it;
				size_t destId = eptr->endId();
				assert( destId != Graph::NOT_A_VERTEX_ID );
				EdgeLength updatedDist = dist[minVertId] + eptr->getAttributes().getLength();
				if ( dist[destId] > updatedDist )
				{
					dist[destId] = updatedDist;
				}
			}
		}
	}

private:
	Graph & gr;
	std::vector< EdgeLength > dist;
};

}
}
}

#endif /* DEJKSTRA_H_ */
